In modern communication systems, e.g., wireless, radio frequency-based networks, communication signals are often transmitted over long distances and at high data transfer rates. For example, in a typical CDMA-based, “1x-EVDO” (Evolution Data Optimized, or Evolution Data Only) wireless network, forward link non-voice data rates (e.g., transmissions from a base station to a wireless unit) are specified up to 3.1 Mbit/sec, with reverse link rates up to 1.8 Mbit/sec in a radio channel dedicated to carrying high-speed packet data, e.g., a 1.25 MHz-bandwidth (or greater) radio channel. Because of the nature of radio wave propagation, with concomitant factors such as wideband Gaussian noise, fading, frequency selectivity, interference, nonlinearity, and dispersion, radio frequency channels tend to be noisy. As a result, a received signal may or may not match the signal as originally transmitted, e.g., the received signal may include one or more errors due to noisy channel conditions. Such errors may be exacerbated at high data transfer rates, and in any event negatively affect the data transfer rate and/or reduce the quality of the wireless transmission.
In an attempt to convey information more reliably through noisy channels, communication systems typically utilize forward error correction (FEC). FEC is a system of error control for data transmission, whereby the transmitting unit adds redundant data to the transmitted signals, which allows the receiving unit to detect and correct errors (within some bound). One method of FEC involves the use of low density parity check (LDPC) codes. LDPC codes are a class of binary (e.g., “1's” and “0's”) linear block codes, whose name derives from the characteristic of the codes' parity-check matrix, which contains only a few 1's in comparison to the amount of 0's. (A parity-check matrix is a matrix/set of 1's and 0's, which, in a simplified sense, can be thought of as a function that maps an input message to an output “code word” for transmission.) LDPC codes have increased in popularity because of their near-capacity performance on a variety of data transmission channels, and because the LDPC decoding function can be implemented with a high degree of algorithmic efficiency.
While the use of LDPC codes is generally advantageous, many LDPC-based methods fail to issue the problem of rate compatibility, i.e., it is preferable that the LDPC coding scheme be compatible across a range of coding rates. Rate-compatible error-correcting codes are useful in a variety of communications engineering settings. For example, hybrid-ARQ is employed to combat fading in cellular systems. Due to channel variability, it is often more efficient to require multiple fast re-transmissions, as provided by hybrid-ARQ protocols, to ensure a successful decoding, rather then provisioning for worst case channel conditions. In the case of wireless vehicular technologies, fading rates are extremely dynamic, and rate-compatible codes are thus well suited for use in such contexts. Another application arises in deep space communication links due to large round-trip times.
Puncturing has been used in certain systems to achieve rate compatibility. Through puncturing, a series of higher rate codes are obtained from a low rate mother code. The encoder generates the full set of parity bits (e.g., bits added to the input message to make a code word), but some are not transmitted (“punctured”). The decoder inserts erasures where parities are punctured and performs the decoding algorithm as in a non-punctured case. Although puncturing may be effective in some cases, the problem with such an approach is two-fold: (1) the mother code is typically optimized for efficient operation at low rates, and subsequently exhibits a widening gap to capacity as the amount of puncturing increases, and (2) optimizations of code structure and puncturing patterns are treated separately, which is suboptimal.